class Solution {
    private static final int INF = (int)1e9;
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        Map<String, Integer> distBegin = new HashMap<>(wordList.size());
        Map<String, Integer> distEnd = new HashMap<>(wordList.size());
        for (String s : wordList) {
            distBegin.put(s, INF);
            distEnd.put(s, INF);
        }
        if (!distBegin.containsKey(endWord)) return 0;
        distBegin.put(beginWord, 1);
        distEnd.put(endWord, 1);
        Queue<String> queueBegin = new LinkedList<>();
        Queue<String> queueEnd = new LinkedList<>();
        queueBegin.offer(beginWord);
        queueEnd.offer(endWord);
        while (!queueBegin.isEmpty() || !queueEnd.isEmpty()) {
            int ans = expand(queueBegin, distBegin, distEnd);
            if (ans != -1) return ans;
            ans = expand(queueEnd, distEnd, distBegin);
            if (ans != -1) return ans;
        }
        return 0;
    }
    private int expand(Queue<String> queue, Map<String, Integer> self, Map<String, Integer> other) {
        if (!queue.isEmpty()) {
            String word = queue.poll();
            char[] arr = word.toCharArray();
            int distanceTop = self.get(word);
            for (int i = 0; i < arr.length; i++) {
                for (int j = 0; j < 26; j++) {
                    char ch = (char)('a' + j);
                    char tmp = arr[i];
                    if (ch == tmp) continue;
                    arr[i] = ch;
                    String newWord = new String(arr);
                    if (self.getOrDefault(newWord, -1) > distanceTop + 1) {
                        self.put(newWord, distanceTop + 1);
                        if (other.get(newWord) != INF) {
                            return distanceTop + other.get(newWord);
                        }
                        queue.offer(newWord);
                    }
                    arr[i] = tmp;
                }
            }
        }
        return -1;
    }
    private int byBFS(String beginWord, String endWord, List<String> wordList) {
        Map<String, Integer> distance = new HashMap<>(wordList.size());
        for (String s : wordList) {
            distance.put(s, INF);
        }
        if (!distance.containsKey(endWord)) return 0;
        distance.put(beginWord, 1);
        Queue<String> queue = new LinkedList<>();
        queue.offer(beginWord);
        while (!queue.isEmpty()) {
            String word = queue.poll();
            char[] arr = word.toCharArray();
            int distanceTop = distance.get(word);
            for (int i = 0; i < arr.length; i++) {
                for (int j = 0; j < 26; j++) {
                    char ch = (char)('a' + j);
                    char tmp = arr[i];
                    if (ch == tmp) continue;
                    arr[i] = ch;
                    String newWord = new String(arr);
                    if (distance.getOrDefault(newWord, -1) > distanceTop + 1) {
                        distance.put(newWord, distanceTop + 1);
                        if (newWord.equals(endWord)) {
                            return distance.get(newWord);
                        }
                        queue.offer(newWord);
                    }
                    arr[i] = tmp;
                }
            }
        }
        return 0;
    }
}
